package xunfei;

import java.util.ArrayList;
import java.util.List;

public class Test3 {
    public static void main(String[] args) {

    }

    /**
     * 迷宫中1表示障碍，0表示路径，8表示奖品，返回最短路径，应该是不能斜着走的
     * 注意边界上的出口
     * @param maze int整型二维数组 迷宫数据 固定为4x4的二维数组，0表示路，可走；1 表示墙，不可通过； 8 表示礼物，是我们的目标
     * @return Point类ArrayList
     */
    int row, col;
    ArrayList<Point> res = new ArrayList<>();
    int[][] directions = {{0,1},{0,-1},{-1,0},{1,0}};
    public ArrayList<Point> winMazeGift (int[][] maze) {
        this.row = maze.length;
        this.col = maze[0].length;
        boolean[][] visited = new boolean[row][col];
        // 遍历所有的入口，只要不是1就进行递归
        for (int i = 0; i < row; i++) {
            if (maze[i][0] != 1) dfs(i,0, maze, visited, new ArrayList<>());
            if (maze[i][col - 1] != 1) dfs(i,col - 1, maze, visited, new ArrayList<>());
        }
        for (int i = 1; i < col - 1; i++) {
            if (maze[0][i] != 1) dfs(0, i, maze, visited, new ArrayList<>());
            if (maze[row - 1][i] != 1) dfs(row - 1, i, maze, visited, new ArrayList<>());
        }
        return res;
    }

    public void dfs(int x, int y, int[][] maze, boolean[][] visited, ArrayList<Point> path){
        visited[x][y] = true;
        path.add(new Point(x, y));
        if (maze[x][y] == 8 && (res.size() == 0 || path.size() < res.size())) {
            res = new ArrayList<>(path);
        }else {
            int newX, newY;
            for (int[] d : directions) {
                newX = x + d[0];
                newY = y + d[1];
                if (valid(newX, newY) && maze[newX][newY] != 1 && !visited[newX][newY]) {
                    dfs(newX, newY, maze, visited, path);
                }
            }
        }
        visited[x][y] = false;
        path.remove(path.size() - 1);
    }
    public boolean valid(int x, int y) {
        return x >= 0 && x < row && y >= 0 && y < col;
    }

    public class Point {
        int x;
        int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}
